package sort;

/**
 * 合并排序算法
 * 合并排序是建立在归并操作上的一种有效的排序算法。该算法是采*用分治法（Divide and Conquer）的一个非常典型的应用。
 *合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，*即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把*有序子序列合并为整体有序序列。
 *将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有*序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为*2-路归并。合并排序也叫归并排序。
 *
 * 一个带排序的原始数据序列进行合并排序的基本思路是，首先将含有*n个结点的待排序数据序列看作有n个长度为1的有序子表组成，将他
 *们两两合并，得到长度为2的若干有序字表；然后再对这些字表进行*两辆合并，得到长度为4的若干有序子表；。。。重复上述过程，一*直重复道最后的子表长度为n,从而完成排序过程
 *
 */
public class MegerSort {
   public static void main(String[] args){
     mergeSort(new int[]{5,4,3,2,1,2,3,4,5},9);
   }
   public static void mergeSort(int[] arr,int size){
       int len = 1;//有序序列的长度
       int f = 0;
       int[] p = new int[size];
       int count = 0;//第几步
       while(len<size){
           if(f==1){
                mergeOne(p,arr,size,len); //p合并到a
           }else{
               mergeOne(arr,p,size,len);    //a合并到p
           }
           len = len * 2;     //增加有序序列的长度
           f = 1-f;      //使f值在0和1之间切换
           count++;  //
           System.out.println("第"+count+"步的排序结果是:");
           for(int h=0;h<arr.length;h++){
               System.out.println(" "+arr[h]);
           }
           System.out.println();
       }
       if(f==1){ //如果进行了排序
           for(int h=0;h<size;h++){
               arr[h]=p[h];
           }
       }

   }

    private static void mergeOne(int[] a, int[] arr, int size, int len) {
        int i,j,k,s,e;
        s = 0;
        while(s+len<size){
            e=s+2*len-1;
            if(e>=size){  //最后一段可能少于len个结点
                e = size -1;
            }
            //相邻有序端合并
            k=s;
            i=s;
            j=s+len;
            while(i<s+len&&j<=e){//如果有两个有序表都未结束时，循环比较
                if(a[i]<=a[j]){//如果较小的元素复制到数组b中
                    arr[k++] = a[i++];
                }else{
                    arr[k++]=a[j++];
                }
            }
            while(i<s+len){  //未合并的部分复制到数组arr中
                arr[k++]=a[i++];
            }
            while(j<=e){
                arr[k++]=a[j++];//未合并的部分复制到数组arr中
            }
            s=e+1;   //下一对有序段中左段的开始下标
        }
       if(s<size){
           for(;s<size;s++){
               arr[s]=a[s];
           }
       }
    }
}
